import java.util.Scanner;

public class day230425 {
    // 淘宝网店

    // 存放每个月的天数
    private static final int[] days = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    // 存放这个月一天的收入
    private static final int[] money = {0, 2, 1, 1, 2, 1, 2, 1, 2, 2, 2, 1, 2};
    // 判断闰年
    private static boolean isLeapYear(int y) {
        return y % 4 == 0 && y % 100 != 0 || y % 400 == 0;
    }
    // 根据 y, m1,d1, m2, d2, 计算这一年的收入
    private static int func(int y, int m1, int d1, int m2, int d2) {
        int result = 0;
        if (m1 == m2) {
            // 同一个月内的收入
            result += (d2 - d1 + 1) * money[m1];
        } else {
            // m1月的收入
            result += (days[m1] - d1 + 1) * money[m1];
            // 中间间隔的月份的收入
            for (int i = m1 + 1; i < m2; i++) {
                result += days[i] * money[i];
            }
            // m2月的收入
            result += d2 * money[m2];
            // 判断2月的情况
            if (m1 <= 2 && m2 > 2 && isLeapYear(y)) {
                result++;
            }
        }
        return result;
    }
    public static void main1(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            int y1 = sc.nextInt();
            int m1 = sc.nextInt();
            int d1 = sc.nextInt();
            int y2 = sc.nextInt();
            int m2 = sc.nextInt();
            int d2 = sc.nextInt();
            int result = 0;
            if (y1 == y2) {
                // 一年内
                result = func(y1, m1, d1, m2, d2);
            } else {
                // 不是同一年
                // y1年的收入
                result = func(y1, m1, d1, 12, 31);
                // 中间间隔的年份的收入
                for (int i = y1 + 1; i < y2; i++) {
                    result += 579;
                    if (isLeapYear(i)) {
                        result++;
                    }
                }
                // y2年的收入
                result += func(y2, 1, 1, m2, d2);
            }
            System.out.println(result);
        }
    }

    // 斐波那契凤尾
    public static void main(String[] args) {
        int[] fib = new int[100000];
        fib[0] = 1;
        fib[1] = 2;
        int x = 0;
        for (int i = 2; i < fib.length; i++) {
            fib[i] = fib[i - 1] + fib[i - 2];
            if (fib[i] > 999999) {
                fib[i] %= 1000000;
            }
            if (fib[i] > 99999 && x == 0) {
                x = i + 1;
            }
        }
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int n = in.nextInt();
            if (n >= x) {
                System.out.printf("%06d\n", fib[n - 1]);
            } else {
                System.out.println(fib[n - 1]);
            }
        }
    }
}
